#include <iostream>
#include "string.h"

using namespace std;

int ValOfShift(const char *substr) {
    const int n = strlen(substr);
    int shift[n];
    int i;
    shift[0] = 0;
    for(i = 1; i < n; i++)
    {
        if(substr[i] == substr[shift[i-1]])
        {
            shift[i] = shift[i-1] + 1;
        }
        else
        {
            shift[i] = 0;
        }
    }

    cout<<"shift is "<<shift[i-1]<<endl;
    return shift[i-1];
}

int kmp(char* mainStr, char* subStr){
    int MainStrLen = strlen(mainStr);
    int SubStrLen = strlen(subStr);
    int shift = ValOfShift(subStr);
    int y;
    for(int i = 0;i<(MainStrLen - SubStrLen);)
    {
        y = i;
        for(int j = 0;j<=SubStrLen;j++, y++)
        {
            if(mainStr[y]!=subStr[j])
            {
                i+=shift;
            //  break;
            }
            else
            {
                cout<<"sr "<<mainStr[y]<<' '<<subStr[j]<<' '<<y<<' '<<j<<endl;
            }
            if(j==SubStrLen)
            {
                return i;
            }
        }

    }
}

int main()
{
    char* mas = "ababbabababaca";
    char* daba = "ababac";
    cout<<kmp(mas,daba);
    return 0;
}
